#include<stdio.h>


void PrintArray(int *a,int size)
{
    for(int i=0;i<size;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
}
//冒泡排序
//O(n^2)
void BubbleSort(int *a,int size)
{
    for(int i=0;i<size-1;i++)//将n个数归位，一共进行n-1轮
    {
        int flag=0;
        for(int j=0;j<size-1-i;j++)//两两比较,冒泡i次后i个数已经归位了不用比较
        {
            if(a[j]>a[j+1])
            {
                flag=1;
                Swap(&a[j],&a[j+1]);
            }
        }
        if(flag==0)//数列已经有序
        {
            break;//跳出循环
        }
    }
}
//插入排序
//O(n^2)
void InsertSort(int *a,int size)
{
    for(int i=1;i<size;i++)
    {
        int j=i;//这个位置是即将要插入的数
        int temp=a[j];
        for(;j>0;j--)
        {
            if(a[j-1]>temp)//前面的数比我大
            {
                a[j]=a[j-1];
            }
             else //前面的数不比我大
            {
            break;
            }
        }
       
        a[j]=temp;
    }
}
//选择排序
void ChooseSort(int *a,int size)
{
    for(int i=0;i<size-1;i++)
    {
        int min=i;
        for(int j=i+1;j<size;j++)
        {
            if(a[min]>a[j])
            {
                min=j;
            }
        }
        Swap(&a[min],&a[i]);
    }
}
void Swap(int *a,int*b)
{
    int temp=*a;
    *a=*b;
    *b=temp;
}

//双指针算法
void ChooseSort2(int *a,int size)
{
    int left=0;
    int right=size-1;
    while(left<right)
    {
        int min=left;
        int max=right;
        for(int i=left;i<=right;i++)
        {
            if(a[i]<a[min])
            {
                min=i;
            }
            if(a[i]>a[max])
            {
                max=i;
            }
        }
        Swap(&a[left],&a[min]);
        if(max==left)//极值在两边
        {
            max=min;
        }
        Swap(&a[right],&a[max]); 
        left++;
        right--;


    }
}


//快速排序  双指针，递归，分治
void  FastSort(int *a,int start,int end)
{
    //终止条件
    if(start>=end)
        return;
    int left=start;
    int right=end;
    int temp=a[start];
    while(left<right)
    {
        //从右往左找基准值小
        while(a[right]>temp&&right>left)
            right--;
        if(left<right)
        {
            a[left++]=a[right];//把比基准值小的数放到左边，在向右++
        }
        while(a[left]<temp&&left<right)
            left++;
        if(left<right)
            a[right--]=a[left];//把比基准值大的放到右边，在向左--
    }
    a[left]=temp;
    FastSort(a,start,left-1);
    FastSort(a,right+1,end);

}
//二分查找
//返回找到数组元素的下标
int BinarySearch(int *a,int size,int element)
{
    int left=0;
    int right=size-1;
    while(left<=right)
    {
        //取中间值
        int mid=left+(right-left)/2;
        //(left&right)+((left^right)>>1);left+(right-left)/2;
        if(a[mid]==element)
        {
            return mid;
        }
        else if(a[mid]>element)
        {
            right=mid-1;''
        }
        else if(a[mid]<element)
        {
            left=mid+1;
        }
    }
        return -1;

}


int main()
{
    int a[8]={3,65,1,46,24,40,100,2};
    PrintArray(a,8);
    FastSort(a,0,7);

    PrintArray(a,8);
    int index=BinarySearch(a,8,46);
    if(index==-1)
    {
        printf("未找到!\n");
    }
    else
    {
        printf("找到了，在%d位置\n",index);
    }

    return 0;
}